{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Matching Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string #binary-search #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串 #二分查找 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numMatchingSubseq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #匹配子序列的单词数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定字符串 <code>s</code>&nbsp;和字符串数组&nbsp;<code>words</code>, 返回&nbsp;&nbsp;<em><code>words[i]</code>&nbsp;中是<code>s</code>的子序列的单词个数</em>&nbsp;。</p>\n",
    "\n",
    "<p>字符串的 <strong>子序列</strong> 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如， <code>“ace”</code> 是 <code>“abcde”</code> 的子序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"abcde\", words = [\"a\",\"bb\",\"acd\",\"ace\"]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 有三个是&nbsp;s 的子序列的单词: \"a\", \"acd\", \"ace\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>Example 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"dsahjpjauf\", words = [\"ahjpjau\",\"ja\",\"ahbwzgqnuk\",\"tnmlanowax\"]\n",
    "<strong>输出:</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 5000</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 50</code></li>\n",
    "\t<li><code>words[i]</code>和 <font color=\"#c7254e\" face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size: 12.6px; background-color: rgb(249, 242, 244);\">s</span></font>&nbsp;都只由小写字母组成。</li>\n",
    "</ul>\n",
    "<span style=\"display:block\"><span style=\"height:0px\"><span style=\"position:absolute\">​​​​</span></span></span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-matching-subsequences](https://leetcode.cn/problems/number-of-matching-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-matching-subsequences](https://leetcode.cn/problems/number-of-matching-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcde\"\\n[\"a\",\"bb\",\"acd\",\"ace\"]', '\"dsahjpjauf\"\\n[\"ahjpjau\",\"ja\",\"ahbwzgqnuk\",\"tnmlanowax\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        dic = collections.defaultdict(list)\n",
    "        for w in words:\n",
    "            dic[w[0]].append(w)\n",
    "        res = 0\n",
    "        for ch in s:\n",
    "            tmp = dic[ch]\n",
    "            dic[ch] = []\n",
    "            for t in tmp:\n",
    "                if len(t) == 1:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    dic[t[1]].append(t[1:])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, S, words):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :type words: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        for word in words:\n",
    "            i = -1\n",
    "            for w in word:\n",
    "                i = S.find(w, i + 1)\n",
    "                if i == -1:\n",
    "                    break\n",
    "            else:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, S, words):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :type words: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        m = collections.defaultdict(list)\n",
    "        for w in words:\n",
    "            it = iter(w)\n",
    "            m[next(it)].append(it)\n",
    "        for c in S:\n",
    "            its = m.pop(c, [])\n",
    "            for it in its:\n",
    "                wc = next(it, None)\n",
    "                if wc is None:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    m[wc].append(it)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n",
    "        count = 0\n",
    "        for word in words:\n",
    "            if self.is_sequence(word,S):\n",
    "                count+=1\n",
    "                # print(word)\n",
    "        return count                                     \n",
    "    def is_sequence(self,word,S):\n",
    "        index = 0\n",
    "        for i in range(len(word)):\n",
    "            res = S.find(word[i],index)\n",
    "            if -1==res:\n",
    "                return False\n",
    "            else:\n",
    "                index = res+1\n",
    "        return True\n",
    "\n",
    "    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n",
    "            waiting = collections.defaultdict(list)\n",
    "            for w in words:\n",
    "                waiting[w[0]].append(iter(w[1:]))  # 存储以w[0]开头的前缀，此时waiting = {'a': [[], ['c', 'd'], ['c', 'e']], 'b': [['b']]}\n",
    "            for c in S:\n",
    "                for it in waiting.pop(c, ()):\n",
    "                    waiting[next(it, None)].append(it)  # 在本题的例子中 it 分别为[]、['c', 'd']、['c', 'e']\n",
    "            return len(waiting[None])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n",
    "        from collections import defaultdict\n",
    "        waiting = defaultdict(list)\n",
    "        for w in words:\n",
    "            waiting[w[0]].append(iter(w[1:]))\n",
    "        for c in S:\n",
    "            for it in waiting.pop(c,()):\n",
    "                waiting[next(it,None)].append(it)\n",
    "        return len(waiting[None])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n",
    "        ans = 0\n",
    "        heads = [[] for _ in range(26)]\n",
    "        for word in words:\n",
    "            # 根据每个单词的第一个字母构建哈希表 key:ord(字母) val:对应的迭代器列表\n",
    "            it = iter(word)\n",
    "            heads[ord(next(it)) - ord('a')].append(it)\n",
    "\n",
    "        for letter in S:\n",
    "            letter_index = ord(letter) - ord('a')\n",
    "            old_bucket = heads[letter_index]\n",
    "            heads[letter_index] = [] # 清空对应的键值对\n",
    "\n",
    "            while old_bucket:\n",
    "                it = old_bucket.pop()\n",
    "                nxt = next(it, None)\n",
    "                if nxt: # 构建新的键值对\n",
    "                    heads[ord(nxt) - ord('a')].append(it)\n",
    "                else: # 说明对应单词遍历完\n",
    "                    ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n",
    "        hash1 = collections.defaultdict(list)\n",
    "        for word in words:\n",
    "            hash1[word[0]].append(iter(word[1:]))\n",
    "        for s in S:\n",
    "            for it in hash1.pop(s, ()):\n",
    "                hash1[next(it,None)].append(it)\n",
    "        return len(hash1[None])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n",
    "        # try2\n",
    "        d = [Queue() for _ in range(26)]\n",
    "        for i, word in enumerate(words):\n",
    "            idx = ord(word[0]) - ord('a')\n",
    "            d[idx].put((i, 0))\n",
    "        res = 0\n",
    "        for si in S:\n",
    "            idx = ord(si) - ord('a')\n",
    "            loop_size = d[idx].qsize()\n",
    "            for _ in range(loop_size):\n",
    "                tmp = d[idx].get()\n",
    "                if tmp[1] == len(words[tmp[0]]) - 1:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    new_idx = ord(words[tmp[0]][tmp[1] + 1]) - ord('a')\n",
    "                    d[new_idx].put([tmp[0], tmp[1]+1])\n",
    "        return res\n",
    "\n",
    "        # try1\n",
    "        d = [[] for _ in range(26)]\n",
    "        for i, si in enumerate(S):\n",
    "            d[ord(si) - ord('a')].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for word in words:\n",
    "            idx = -1\n",
    "            for w in word:\n",
    "                j = bisect.bisect_left(d[ord(w) - ord('a')], idx)\n",
    "                if j == len(d[ord(w) - ord('a')]):\n",
    "                    break\n",
    "                idx = d[ord(w) - ord('a')][j] + 1\n",
    "            else:\n",
    "                res += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        count = 0\n",
    "        for word in words:\n",
    "            num = 0\n",
    "            pos = -1\n",
    "            for c in word:\n",
    "                pos = s.find(c, pos + 1)\n",
    "                if pos == -1:\n",
    "                    break\n",
    "                else:\n",
    "                    num += 1\n",
    "            if num == len(word):\n",
    "                count += 1\n",
    "        return count \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        cnt = 0\n",
    "        for each in words:\n",
    "            len_each = len(each)\n",
    "            if len_each>len(s):\n",
    "                continue\n",
    "            i_idx = 0\n",
    "            for i in range(len_each):\n",
    "                if each[i] in s[i_idx:]:\n",
    "                    if i == (len_each-1):\n",
    "                        cnt = cnt + 1\n",
    "                        break\n",
    "                    i_idx = s[i_idx:].index(each[i])+i_idx+1\n",
    "                else:\n",
    "                    break\n",
    "                if i_idx == len(s):\n",
    "                    break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        cnt = 0\n",
    "        # 统计一下是否有重复词汇，如果有，我们只需要判断一次\n",
    "        wordsn = dict()\n",
    "        for w in words:\n",
    "            if not w in wordsn:\n",
    "                wordsn[w] = 1\n",
    "            else:\n",
    "                wordsn[w] += 1\n",
    "\n",
    "        for word, v in wordsn.items():\n",
    "            # 因为是子串，所以如果word长度都大于s了，直接跳过\n",
    "            if len(word) > len(s): continue\n",
    "\n",
    "            # 为s和word分别初始化一个指针\n",
    "            curw, curs = 0, 0\n",
    "            while curw < len(word) and curs < len(s):\n",
    "                if word[curw] == s[curs]:\n",
    "                    curw += 1\n",
    "                curs += 1\n",
    "            if curw == len(word):\n",
    "                cnt += v\n",
    "\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        def isSub(sent, word) -> bool:\n",
    "            i, j = 0, 0\n",
    "            while i < len(sent) and j < len(word):\n",
    "                if word[j] == sent[i]:\n",
    "                    j += 1\n",
    "                i += 1\n",
    "            return j == len(word)\n",
    "        \n",
    "        c = Counter(words)\n",
    "        count = 0\n",
    "        for k, v in c.items():\n",
    "            count += v if isSub(s, k) else 0\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        res = len(words)\n",
    "        cnt = Counter(words)\n",
    "        for word in cnt:\n",
    "            i = 0\n",
    "            for c in word:\n",
    "                i = s.find(c, i) + 1\n",
    "                if not i:\n",
    "                    res -= cnt[word]\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        res = len(words)\n",
    "        cnt = Counter(words)\n",
    "        for k in cnt:\n",
    "            i = 0\n",
    "            for c in k:\n",
    "                i = s.find(c, i) + 1\n",
    "                if not i:\n",
    "                    res -= cnt[k]\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        points = [0] * len(words)\n",
    "        bags = [[] for _ in range(26)]\n",
    "        for i, w in enumerate(words):\n",
    "            bags[ord(w[0]) - ord('a')].append(i)\n",
    "    \n",
    "        ans = 0\n",
    "        for si in s:\n",
    "            print(ord(si) - ord('a'))\n",
    "            tmp = []\n",
    "            for i in bags[ord(si) - ord('a')]:\n",
    "                points[i] += 1\n",
    "                if points[i] != len(words[i]):\n",
    "                    tmp.append(i)\n",
    "                else:\n",
    "                    ans += 1\n",
    "            bags[ord(si) - ord('a')] = []\n",
    "            for i in tmp:\n",
    "                bags[ord(words[i][points[i]]) - ord('a')].append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        p = defaultdict(list)\n",
    "        for i, w in enumerate(words):\n",
    "            p[w[0]].append((i,0)) # for each word, save the first alpha\n",
    "        res = 0\n",
    "        for c in s:\n",
    "            q = p[c]\n",
    "            p[c] = []\n",
    "            for i, j in q:\n",
    "                j += 1\n",
    "                if j == len(words[i]):\n",
    "                    res += 1\n",
    "                else:\n",
    "                    p[words[i][j]].append((i, j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        # 桶方法，每个桶key值为当前桶所有单词的首字母，每遇到一个字符，将桶中对应单词首字母去掉，然后重新装入桶，当桶长度为1时，符合\n",
    "        bucket = defaultdict(list)\n",
    "        for w in words:\n",
    "            bucket[w[0]].append(w)\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if c in bucket:\n",
    "                wList = bucket[c]\n",
    "                bucket[c] = []\n",
    "                for curW in wList:\n",
    "                    if len(curW) == 1:\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        bucket[curW[1]].append(curW[1:])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            mp[c].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for word in words:\n",
    "            cur_idx = -1\n",
    "            for c in word:\n",
    "                if not mp[c] or mp[c][-1] <= cur_idx:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "\n",
    "                cur_idx = mp[c][bisect_right(mp[c], cur_idx)]\n",
    "\n",
    "            ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        def bisect_right(nums, target):\n",
    "            left = 0\n",
    "            right = len(nums)\n",
    "            while left < right:\n",
    "                mid = (left + right)//2\n",
    "                if nums[mid] > target:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "        d = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            d[c].append(i)\n",
    "        ans = len(words)\n",
    "        for word in words:\n",
    "            if len(word) > len(s):\n",
    "                ans = ans - 1\n",
    "                continue\n",
    "            p = -1\n",
    "            for c in word:\n",
    "                pos = bisect_right(d[c], p)\n",
    "                if pos == len(d[c]):\n",
    "                    ans = ans - 1\n",
    "                    break\n",
    "                p = d[c][pos]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def is_sub(self, s_map, word):\n",
    "        last_idx = -1\n",
    "        n = len(word)\n",
    "        for ch in word:\n",
    "            if ch not in s_map:\n",
    "                return False\n",
    "            ch_list = s_map[ch]\n",
    "            r_idx = ch_list.bisect_right(last_idx)\n",
    "            if r_idx >= len(ch_list):\n",
    "                return False\n",
    "            last_idx = ch_list[r_idx]\n",
    "        return True\n",
    "        \n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        s_map = dict()\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch not in s_map:\n",
    "                s_map[ch] = SortedList()\n",
    "            s_map[ch].add(i)\n",
    "        \n",
    "        res = 0\n",
    "        for word in words:\n",
    "            if self.is_sub(s_map, word):\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # binary search, return the pos to the right of idx of target\n",
    "    def binarySearch(self,nums,target):\n",
    "        l,r = 0, len(nums)-1\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0 if target < nums[0] else 1\n",
    "        while l < r:\n",
    "            mid = (l+r)>>1\n",
    "            if nums[mid]>target:\n",
    "                r = mid\n",
    "            elif nums[mid]<target:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                return mid+1\n",
    "\n",
    "        return l\n",
    "\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        # define a dic to record the position of each char in s\n",
    "        pos = collections.defaultdict(list)\n",
    "        for idx, c in enumerate(s):\n",
    "            pos[c].append(idx)\n",
    "        print(pos)\n",
    "\n",
    "        count = len(words)\n",
    "        for w in words:\n",
    "            if len(w)>len(s):\n",
    "                count -= 1\n",
    "                continue\n",
    "            pre = -1\n",
    "            \n",
    "            for char in w:\n",
    "                cur = bisect_right(pos[char],pre)\n",
    "                # cur = self.binarySearch(pos[char],pre)\n",
    "                print(char, cur)\n",
    "                if cur==len(pos[char]):\n",
    "                    count -= 1\n",
    "                    # 直接退出当前word的循环\n",
    "                    break\n",
    "                    print(char, count)\n",
    "                # pre记录上一个字符在s中的索引\n",
    "                # cur 是pos[char]的索引值\n",
    "                pre = pos[char][cur]\n",
    "\n",
    "        return count\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        import bisect\n",
    "\n",
    "        m = len(s)\n",
    "        cnt = defaultdict(list)\n",
    "        for idx, c in enumerate(s):\n",
    "            cnt[c].append(idx)\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        def check(word):\n",
    "            i = 0 \n",
    "            for c in word:\n",
    "                idx = bisect_left(cnt[c],i)\n",
    "                if idx == len(cnt[c]):\n",
    "                    return False\n",
    "                i = cnt[c][idx] + 1\n",
    "\n",
    "            return True\n",
    "                \n",
    "\n",
    "\n",
    "        for word in words:\n",
    "            if len(word) > len(s):\n",
    "                continue\n",
    "\n",
    "            if check(word) == True:\n",
    "                print(word,count)\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        # 诀窍：二分法\n",
    "        m = len(s)\n",
    "        ans = 0\n",
    "        # 1. 把s中每个字符出现的位置记录下来\n",
    "        index_dict = {}\n",
    "        for i in range(m):\n",
    "            if s[i] not in index_dict:\n",
    "                index_dict[s[i]] = [i]\n",
    "            else:\n",
    "                index_dict[s[i]].append(i)\n",
    "        print(index_dict)\n",
    "        for word in words:\n",
    "            j = 0 # 串s的指针\n",
    "            n = len(word)\n",
    "            is_subsequence = True\n",
    "            for i in range(n):\n",
    "                c = word[i]\n",
    "                if c not in index_dict: # s不包含\n",
    "                    is_subsequence = False\n",
    "                    break\n",
    "                pos = self.left_bound(index_dict[c], j) \n",
    "                if pos == -1: # s[j:]不包含c\n",
    "                    is_subsequence = False\n",
    "                    break\n",
    "                j = pos + 1 # s下一轮的位置开头\n",
    "            if is_subsequence: # 是子序列\n",
    "                ans += 1\n",
    "        return ans\n",
    "    \n",
    "    def left_bound(self, nums, target):\n",
    "        # 返回nums, 元素>target的最小下标\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "        while(left <= right):\n",
    "            mid = left + (right-left)//2\n",
    "            if nums[mid] >= target:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        if left<len(nums) and nums[left] >= target:\n",
    "            return nums[left]\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        \n",
    "        ret = 0\n",
    "        for word in words:\n",
    "            if self.isMatching(s, word):\n",
    "                ret += 1\n",
    "        return ret\n",
    "    @cache\n",
    "    def isMatching(self, s, word):\n",
    "            i, j = 0, 0\n",
    "            while i < len(s) and j < len(word):\n",
    "                if i < len(s) and s[i] == word[j]:\n",
    "                    j += 1\n",
    "                i += 1\n",
    "            return j == len(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def isSubseq(self, s1, s2):\n",
    "        n1, n2 = len(s1), len(s2)\n",
    "        point1, point2 = 0, 0\n",
    "        while point1 < n1 and point2 < n2:\n",
    "            if s1[point1] == s2[point2]:\n",
    "                point1 += 1\n",
    "                point2 += 1\n",
    "                if point2 == n2:\n",
    "                    return True\n",
    "            elif s1[point1] != s2[point2]:\n",
    "                point1 += 1\n",
    "        return False\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        count = 0\n",
    "        for s2 in words:\n",
    "            if self.isSubseq(s, s2):\n",
    "                count +=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        \"\"\"\n",
    "        find #is_subseq(s, word[i]) in words\n",
    "        \"\"\"\n",
    "        from collections import defaultdict\n",
    "\n",
    "        def is_subseq(word: str) -> bool:\n",
    "            \"\"\"\n",
    "            Check whether word is a subsequence of s\n",
    "\n",
    "            ==> Two-pointer + binary search\n",
    "\n",
    "            Specifically, for any char in word,\n",
    "\n",
    "            We need to FIND NEXT p_s in mapping[char] \n",
    "\n",
    "            However, to speed up the lookup, we can use binary search\n",
    "\n",
    "            on (p_s, len(s)) to find the left boundary of (p_s, len(s))\n",
    "            \"\"\"\n",
    "\n",
    "            def next_element(start: int,\n",
    "                             end: int,\n",
    "                             target: int) -> Optional[int]:\n",
    "                \"\"\"\n",
    "                Find the index of next element > target in candidates[start: end + 1]\n",
    "                \"\"\"\n",
    "                if start > end:\n",
    "                    return None\n",
    "                if candidates[end] < target:\n",
    "                    return None\n",
    "                if candidates[start] > target:\n",
    "                    return candidates[start]\n",
    "\n",
    "                mid = (start + end) // 2\n",
    "                if target >= candidates[mid]:\n",
    "                    return next_element(mid + 1, end, target)\n",
    "\n",
    "                # target < candidates[mid]\n",
    "                return next_element(start, mid, target)\n",
    "\n",
    "            p_s = -1\n",
    "            # Loop over the word to match\n",
    "            for char in word:\n",
    "                # Skip all unnecessary indices\n",
    "                # Should jump to the first candidate > p_s\n",
    "                candidates = char_to_indices[char]\n",
    "                p_s = next_element(0, len(candidates) - 1, p_s)\n",
    "                if p_s is None:\n",
    "                    return False\n",
    "\n",
    "            return True\n",
    "\n",
    "        # Preprocess on s: mapping [char -> list of indices]\n",
    "        # Notice that indices are sorted (prerequisite of binary search)\n",
    "        char_to_indices = defaultdict(list)\n",
    "        for index, char in enumerate(s):\n",
    "            char_to_indices[char].append(index)\n",
    "\n",
    "        # Find #subseq\n",
    "        n_subseq = 0\n",
    "        for word in words:\n",
    "            if len(word) > len(s):\n",
    "                continue\n",
    "            if is_subseq(word):\n",
    "                n_subseq += 1\n",
    "\n",
    "        return n_subseq\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        result, trie = 0, {}\n",
    "        for word in words:\n",
    "            cur = reduce(lambda d, c: d.setdefault(c, {}), word, trie)\n",
    "            cur['!'] = cur.get('!', 0) + 1\n",
    "        d = defaultdict(list)\n",
    "        for c in trie:\n",
    "            d[c].append(trie[c])\n",
    "        for c in s:\n",
    "            next_arr = []\n",
    "            while d[c]:\n",
    "                sub = d[c].pop()\n",
    "                for c2 in sub:\n",
    "                    if c2 == '!':\n",
    "                        result += sub['!']\n",
    "                    elif c2 != c:\n",
    "                        d[c2].append(sub[c2])\n",
    "                    else:\n",
    "                        next_arr.append(sub[c2])\n",
    "            d[c] = next_arr\n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        root={}\n",
    "        def mktr(w):\n",
    "            nd=root\n",
    "            for c in w:\n",
    "                if c not in nd:\n",
    "                    nd[c]={}\n",
    "                nd=nd[c]\n",
    "            if '.' not in nd:\n",
    "                nd['.']=0\n",
    "            nd['.']+=1\n",
    "        for w in words:\n",
    "            mktr(w)\n",
    "        res=0\n",
    "        cand=defaultdict(list)\n",
    "        for k,v in root.items():\n",
    "            cand[k].append(v)\n",
    "        # print(cand['b'],root)\n",
    "        for c in s:\n",
    "            lt,cand[c]=cand[c],[]\n",
    "            for d1 in lt:\n",
    "                for k,v in list(d1.items()):\n",
    "                    if k=='.':\n",
    "                        res+=v\n",
    "                    #     del d1[k]\n",
    "                    # elif len(v)==0:\n",
    "                    #     del d1[k]\n",
    "                    else:\n",
    "                        cand[k].append(v)\n",
    "                    # print(k,v,len(cand['b']))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        dict_tree = {}\n",
    "        self.ans = 0\n",
    "        for word in words:\n",
    "            d = dict_tree\n",
    "            for char in word:\n",
    "                if char not in d:\n",
    "                    d[char] = {}\n",
    "                d = d[char]\n",
    "            if 'end' not in d:\n",
    "                d['end'] = 1\n",
    "            else:\n",
    "                d['end'] += 1\n",
    "        # print(dict_tree)\n",
    "        def search(d, start, end):\n",
    "            # if d == 'end':\n",
    "            #     self.ans += 1\n",
    "            #     print('here')\n",
    "            for k,v in d.items():\n",
    "                if k == 'end':\n",
    "                    self.ans += v\n",
    "                    # print('end')\n",
    "                    continue\n",
    "                for i in range(start, end):\n",
    "                    if s[i] == k:\n",
    "                        # print(k)\n",
    "                        search(v, i+1, end)\n",
    "                        # visited.add(k)\n",
    "                        break\n",
    "        search(dict_tree, 0, len(s))\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        dic = {}\n",
    "\n",
    "        def makeDict(d: dict, s: str):\n",
    "            if len(s) == 0:\n",
    "                if '#' not in d:\n",
    "                    d['#'] = 1\n",
    "                else:\n",
    "                    d['#'] += 1\n",
    "            else:\n",
    "                c, ns = s[0], s[1:]\n",
    "                if c not in d:\n",
    "                    d[c] = {}\n",
    "                makeDict(d[c], ns)\n",
    "\n",
    "        def update(old: dict, new: dict):\n",
    "            for key, value in new.items():\n",
    "                if key in old:\n",
    "                    if key == '#':\n",
    "                        old['#'] += value\n",
    "                    else:\n",
    "                        update(old[key], value)\n",
    "                else:\n",
    "                    old[key] = value\n",
    "\n",
    "        for word in words:\n",
    "            makeDict(dic, word)\n",
    "        for c in s:\n",
    "            if c in dic:\n",
    "                update(dic, dic.pop(c))\n",
    "        return dic['#']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def dfs(t, sidx):\n",
    "            if '#' in t:\n",
    "                self.res += t['#']\n",
    "            for ch in t:\n",
    "                eidx = s.find(ch, sidx) + 1\n",
    "                if eidx:\n",
    "                    dfs(t[ch], eidx)\n",
    "            \n",
    "        trie = {}\n",
    "        for word in words:\n",
    "            t = trie\n",
    "            for ch in word:\n",
    "                if ch not in t:\n",
    "                    t[ch] = {}\n",
    "                t = t[ch]\n",
    "            t['#'] = t.get('#', 0) + 1\n",
    "        self.res = 0\n",
    "        dfs(trie, 0)\n",
    "        return self.res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #two points, binary search\n",
    "    # def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "    #     postions = {}\n",
    "    #     for i in range(len(s)):\n",
    "    #         if s[i] not in postions:\n",
    "    #             postions[s[i]] = []\n",
    "    #         postions[s[i]].append(i)\n",
    "    #     def is_match(s, word):\n",
    "    #         m, n = len(s), len(word)\n",
    "    #         i, j = 0, 0\n",
    "    #         while i < m and j < n:\n",
    "    #             if s[i] != word[j]:\n",
    "    #                 if word[j] not in postions:\n",
    "    #                     return False\n",
    "    #                 pos = postions[word[j]]\n",
    "    #                 left, right = 0, len(pos)\n",
    "    #                 while left < right:\n",
    "    #                     mid = (left + right) // 2\n",
    "    #                     if pos[mid] < i:\n",
    "    #                         left = mid + 1\n",
    "    #                     else:\n",
    "    #                         right = mid\n",
    "    #                 if right == len(pos):\n",
    "    #                     return False\n",
    "    #                 i = pos[right]\n",
    "    #             else:\n",
    "    #                 i += 1\n",
    "    #                 j += 1\n",
    "    #         return j == n\n",
    "    #     res = 0\n",
    "    #     for word in words:\n",
    "    #         if is_match(s, word):\n",
    "    #             res += 1\n",
    "    #     return res\n",
    "    # bucket\n",
    "    # def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "    #     bucket = {}\n",
    "    #     for word in words:\n",
    "    #         ch = word[0]\n",
    "    #         if ch not in bucket:\n",
    "    #             bucket[ch] = deque()\n",
    "    #         bucket[ch].append(word)\n",
    "    #     res = 0\n",
    "    #     for ch in s:\n",
    "    #         if ch not in bucket:\n",
    "    #             continue\n",
    "    #         for _ in range(len(bucket[ch])):\n",
    "    #             ch1 = bucket[ch].popleft()\n",
    "    #             if len(ch1) == 1:\n",
    "    #                 res += 1\n",
    "    #             else:\n",
    "    #                 if ch1[1] not in bucket:\n",
    "    #                     bucket[ch1[1]] = deque()\n",
    "    #                 bucket[ch1[1]].append(ch1[1:])\n",
    "    #     return res\n",
    "\n",
    "\n",
    "    #trie, wrong\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        root = {}\n",
    "        for word in words:\n",
    "            node = root\n",
    "            for ch in word:\n",
    "                if ch not in node:\n",
    "                    node[ch] = {}\n",
    "                node = node[ch]\n",
    "            node['#'] = node.get('#', 0) + 1\n",
    "        def dfs1(i, node):\n",
    "            res = 0\n",
    "            if i == len(s):\n",
    "                if '#' in node:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if s[i] in node:\n",
    "                res += dfs(i+1, node[s[i]])\n",
    "            res += dfs(i+1, node)\n",
    "            return res     \n",
    "        def dfs(i, node):\n",
    "            res = 0\n",
    "            if '#' in node:\n",
    "                res += node['#']\n",
    "            if i == len(s):\n",
    "                return res\n",
    "            for key in node:\n",
    "                if key == '#':\n",
    "                    continue\n",
    "                if s.find(key, i) != -1:\n",
    "                    res += dfs(s.find(key, i)+1, node[key])\n",
    "            return res\n",
    "\n",
    "        return dfs(0, root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        trie={}\n",
    "        for w in words:\n",
    "            cur=trie\n",
    "            for c in w:\n",
    "                if c not in cur:cur[c]={}\n",
    "                cur=cur[c]\n",
    "            cur[\"#\"]=cur.get(\"#\",0)+1\n",
    "        self.res=0\n",
    "        def dfs(cur,srr):\n",
    "            if not srr:return\n",
    "            for c in cur.keys():\n",
    "                if c==\"#\":\n",
    "                    self.res+=cur[c]\n",
    "                elif c==srr[0]:\n",
    "                    dfs(cur[c],srr[1:])\n",
    "                elif c in srr:\n",
    "                    i=srr.index(c)\n",
    "                    dfs(cur[c],srr[i+1:])\n",
    "        dfs(trie,s+\"?\")\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        dicT = [0, {}]\n",
    "        for x in words:\n",
    "            pres = dicT\n",
    "            for y in x:\n",
    "                if y not in pres[1]:\n",
    "                    pres[1][y] = [0, {}]\n",
    "                pres = pres[1][y]\n",
    "            pres[0] += 1\n",
    "        dic, res = {x: [dicT[1][x]] for x in dicT[1]}, 0\n",
    "        for z in s:\n",
    "            if z in dic:\n",
    "                pres = dic[z][:]\n",
    "                dic[z] = []\n",
    "                for x in pres:\n",
    "                    res += x[0]\n",
    "                    for y in x[1]:\n",
    "                        dic.setdefault(y, []).append(x[1][y])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        N = len(s)\n",
    "        locMap = [(N + 1) * [-1] for _ in range(26)]\n",
    "        for i, c in enumerate(s):\n",
    "            locList = locMap[ord(c) - ord('a')]\n",
    "            cur = i\n",
    "            while cur >= 0 and locList[cur] == -1:\n",
    "                locList[cur] = i\n",
    "                cur -= 1\n",
    "\n",
    "        def query(word):\n",
    "            cur = 0\n",
    "            for c in word:\n",
    "                cur = locMap[ord(c) - ord('a')][cur] + 1\n",
    "                if not cur: return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(query, words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[-1] * (n + 1) for i in range(26)]\n",
    "        for j in range(len(s)-2, -2, -1):\n",
    "            for i in range(26):\n",
    "                dp[i][j] = dp[i][j+1]\n",
    "            r = ord(s[j+1]) - ord('a')\n",
    "            dp[r][j] = j+1\n",
    "\n",
    "        def judFunc(goal: str) -> bool:\n",
    "            c = -1\n",
    "            for i, ch in enumerate(goal):\n",
    "                r = ord(ch) - ord('a')\n",
    "                if dp[r][c] == -1:\n",
    "                    return False\n",
    "                c = dp[r][c]\n",
    "            return True\n",
    "        ans = 0\n",
    "        for w in words:\n",
    "            if judFunc(w):\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        valid_next_chr = defaultdict(set)\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                valid_next_chr[word[:i]].add(word[i])\n",
    "            valid_next_chr[word].add('')\n",
    "        count = Counter(words)\n",
    "        res = 0\n",
    "        current_valid_subsequence = {\"\"}\n",
    "        current_valid_next_chr = defaultdict(list, {i: [\"\"] for i in valid_next_chr[\"\"]})\n",
    "        \n",
    "        for chr in s:\n",
    "            if chr not in current_valid_next_chr:\n",
    "                continue\n",
    "            else:\n",
    "                for prefix in current_valid_next_chr.pop(chr):\n",
    "                    valid_next_chr[prefix].remove(chr)\n",
    "                    if not valid_next_chr[prefix]:\n",
    "                        current_valid_subsequence.remove(prefix)\n",
    "                    if \"\" in valid_next_chr[prefix + chr]:\n",
    "                        res += count[prefix + chr]\n",
    "                        valid_next_chr[prefix + chr].remove(\"\")\n",
    "                    if valid_next_chr[prefix + chr]:\n",
    "                        current_valid_subsequence.add(prefix + chr)\n",
    "                        for next_chr in valid_next_chr[prefix + chr]:\n",
    "                            current_valid_next_chr[next_chr].append(prefix + chr)\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        dp = [[-1 for _ in range(len(s))] for _ in range(26)]\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(26):\n",
    "                k = chr(j+ord('a'))\n",
    "                if k == s[i]:\n",
    "                    dp[j][i] = i\n",
    "                else:\n",
    "                    if i+1 >= len(dp[j]):\n",
    "                        dp[j][i] = -1\n",
    "                    else:\n",
    "                        dp[j][i] = dp[j][i+1]\n",
    "        # print(dp)\n",
    "        res = 0\n",
    "        for word in words:\n",
    "            flag = True\n",
    "            j = ord(word[0]) - ord('a')\n",
    "            cur_i = dp[j][0] + 1\n",
    "            for c in word[1:]:\n",
    "                j = ord(c) - ord('a')\n",
    "                if cur_i < 0:\n",
    "                    flag = False\n",
    "                    break\n",
    "                elif cur_i >= len(s):\n",
    "                    flag = False\n",
    "                    break\n",
    "                elif dp[j][cur_i] < cur_i:\n",
    "                    flag = False\n",
    "                    break\n",
    "                else:\n",
    "                    cur_i = dp[j][cur_i] + 1\n",
    "            if flag:\n",
    "                res += 1\n",
    "                # print(word)\n",
    "        return res\n",
    "                \n",
    "# class Solution:\n",
    "#     def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "#         def check(w):\n",
    "#             i = -1\n",
    "#             for c in w:\n",
    "#                 j = bisect_right(d[c], i)\n",
    "#                 if j == len(d[c]):\n",
    "#                     return False\n",
    "#                 i = d[c][j]\n",
    "#             return True\n",
    "\n",
    "#         d = defaultdict(list)\n",
    "#         for i, c in enumerate(s):\n",
    "#             d[c].append(i)\n",
    "#         return sum(check(w) for w in words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class TrieNode:\n",
    "        def __init__(self):\n",
    "            self.nodes = {}\n",
    "            self.leaf = 0\n",
    "\n",
    "        def insert(self, str):\n",
    "            cur = self\n",
    "\n",
    "            for s in str:\n",
    "                if s not in cur.nodes:\n",
    "                    cur.nodes[s] = Solution.TrieNode()\n",
    "                cur = cur.nodes[s]\n",
    "\n",
    "            cur.leaf += 1\n",
    "\n",
    "    def dfs(self, root, s, offset):\n",
    "        for key in root.nodes:\n",
    "            pos = s.find(key, offset)\n",
    "\n",
    "            if pos >= offset:\n",
    "                self.res += root.nodes[key].leaf\n",
    "                self.dfs(root.nodes[key], s, pos + 1)\n",
    "\n",
    "\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        root = Solution.TrieNode()\n",
    "\n",
    "        for w in words:\n",
    "            root.insert(w)\n",
    "\n",
    "        self.res = 0\n",
    "        self.dfs(root, s, 0)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.child = collections.defaultdict(Trie)\n",
    "        self.isWord = 0\n",
    "        self.word = \"\"\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            p = trie\n",
    "            for c in word:\n",
    "                p = p.child[c]\n",
    "            p.isWord += 1\n",
    "            p.word = word\n",
    "        self.ans = 0\n",
    "        def dfs(word, start, node):\n",
    "            if node.isWord:\n",
    "                self.ans += node.isWord\n",
    "\n",
    "            if start == len(word):\n",
    "                return\n",
    "            \n",
    "            for c in node.child:\n",
    "                ind = word.find(c, start)\n",
    "                if ind != -1:\n",
    "                    dfs(word, ind+1, node.child[c])\n",
    "        dfs(s, 0, trie)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cache = dict()\n",
    "        self.detail_cache = dict()\n",
    "\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        return sum([self.subseq(s, word) for word in words])\n",
    "\n",
    "    def subseq(self, s, word):\n",
    "        if word in self.cache:\n",
    "            return self.cache[word]\n",
    "        i, j = 0, 0\n",
    "        s_len = len(s)\n",
    "        word_len = len(word)\n",
    "        detailed_c_keys = []\n",
    "        while i < s_len and j < word_len:\n",
    "            if s[i] == word[j]:\n",
    "                for c_key in detailed_c_keys:\n",
    "                    self.detail_cache[c_key] = i\n",
    "                    detailed_c_keys = []\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                c_key = (i, word[j])\n",
    "                if c_key in self.detail_cache:\n",
    "                    i = self.detail_cache[c_key]\n",
    "                else:\n",
    "                    detailed_c_keys.append(c_key)\n",
    "                    i += 1\n",
    "        res = 1 if j == word_len else 0\n",
    "        self.cache[word] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        wlen = len(s)\n",
    "        idxs = [[]] * wlen\n",
    "        bs = [-1] * 26\n",
    "\n",
    "        def o(w):\n",
    "            return ord(w) - 97\n",
    "        \n",
    "        for i in range(wlen-1, -1, -1):\n",
    "            idxs[i] = tuple(bs)\n",
    "            bs[o(s[i])] = i\n",
    "        bidxs = tuple(bs)\n",
    "            \n",
    "        # pp(' '.join(str(i) for i in bidxs))\n",
    "        # for s in idxs:\n",
    "        #     pp(' '.join(str(i) for i in s))\n",
    "\n",
    "        def fc(w):\n",
    "            b = bidxs[o(w[0])]\n",
    "            if b < 0:\n",
    "                return False\n",
    "            for ws in w[1:]:\n",
    "                b = idxs[b][o(ws)]\n",
    "                if b < 0:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        cnt = 0\n",
    "        for w in words:\n",
    "            if fc(w):\n",
    "                cnt += 1\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TNode:                         #字典树结点类型\n",
    "    def __init__(self):\n",
    "        self.ch=[None]*26\n",
    "        self.cnt=0                          #表示该结点代表的字母出现了多少次\n",
    "        self.isend=False\n",
    "class Trie:            #字典树类\n",
    "    def __init__(self):\n",
    "        self.root=TNode()       #根结点\n",
    "    def insert(self,s):                         #向root中插入字符串s\n",
    "        p=self.root\n",
    "        for c in s:\n",
    "            if p.ch[ord(c)-ord('a')]==None:\n",
    "                p.ch[ord(c)-ord('a')]=TNode()\n",
    "            p=p.ch[ord(c)-ord('a')]\n",
    "        p.cnt+=1\n",
    "    def dfs(self,root,s,pos):   #深度优先搜索字典树\n",
    "        ans=0\n",
    "        if root.cnt>0:\n",
    "            ans+=root.cnt\n",
    "            root.cnt=0           #避免重复查找\n",
    "        for k in range(0,26):\n",
    "            if root.ch[k]:\n",
    "                nextpos=s.find(chr(ord('a')+k),pos)\n",
    "                if nextpos!=-1:\n",
    "                    ans+=self.dfs(root.ch[k],s,nextpos+1)\n",
    "        return ans\n",
    "    def Count(self,s):           #求字典树中s子序列的个数\n",
    "        return self.dfs(self.root,s,0)\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        tr=Trie()                #定义字典树对象\n",
    "        for word in words:\n",
    "            tr.insert(word);\n",
    "        return tr.Count(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        # 参考题「392. 判断子序列」的动归方法\n",
    "        n = len(s)\n",
    "        dp = [[0] * 26 for _ in range(n)]\n",
    "        dp.append([n] * 26)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(26):\n",
    "                dp[i][j] = i if ord(s[i]) - ord('a') == j else dp[i + 1][j]\n",
    "        \n",
    "        ans = 0\n",
    "        for w in words: # 遍历每一个单词\n",
    "            if len(w) > n: # 单词太长\n",
    "                continue\n",
    "            tmp = 1 # 临时变量，如果这个单词满足条件，那么数目就会加1，否则tmp=0，数目加0\n",
    "            i = 0\n",
    "            for c in w: # 遍历单词每一个字母\n",
    "                if dp[i][ord(c) - ord('a')] == n: # 当前字母不在字符串中\n",
    "                    tmp = 0\n",
    "                    break\n",
    "                i = dp[i][ord(c) - ord('a')] + 1\n",
    "            ans += tmp\n",
    "\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "        # # 分桶（多指针同时匹配s）\n",
    "        # # 将 words 中的所有单词根据首字母来分桶，即：把所有单词按照首字母分到 26 个桶中，每个桶中存储的是所有以该字母开头的所有单词\n",
    "        # # 比如对于 words = [\"a\", \"bb\", \"acd\", \"ace\"]，我们得到以下的分桶结果：\n",
    "        # # a: [\"a\", \"acd\", \"ace\"]  b: [\"bb\"]\n",
    "        # # 然后我们从 s 的第一个字符开始遍历，假设当前字符为 'a'，我们从 'a' 开头的桶中取出所有单词。\n",
    "        # # 对于取出的每个单词，如果此时单词长度为 1，说明该单词已经匹配完毕，我们将答案加 1；\n",
    "        # # 否则我们将单词的首字母去掉，然后放入下一个字母开头的桶中，\n",
    "        # # 比如对于单词 \"acd\"，去掉首字母 'a' 后，我们将其放入 'c' 开头的桶中。这一轮结束后，分桶结果变为：\n",
    "        # # c: [\"cd\", \"ce\"]  b: [\"bb\"]\n",
    "        # # 遍历完 s 后，我们就得到了答案\n",
    "        # # 实际上，每个桶可以只存储单词的下标 i 以及该单词当前匹配到的位置 j，这样可以节省空间。\n",
    "        # d = defaultdict(deque)\n",
    "        # for i, w in enumerate(words):\n",
    "        #     d[w[0]].append((i, 0))\n",
    "        # ans = 0\n",
    "        # for c in s:\n",
    "        #     for _ in range(len(d[c])): # 遍历字符c的桶\n",
    "        #         i, j = d[c].popleft() # 单词，以及字符c在单词中的下标\n",
    "        #         j += 1 # 下标后移\n",
    "        #         if j == len(words[i]): # 后移结果超过最大下标，单词匹配完了\n",
    "        #             ans += 1\n",
    "        #         else: # 没有匹配完，按照下标后移之后的单词的字符，将单词放入对应的桶中\n",
    "        #             d[words[i][j]].append((i, j))\n",
    "        # return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_right\n",
    "from collections import defaultdict\n",
    "from typing import DefaultDict, Generic, List, Sequence, Tuple, TypeVar\n",
    "\n",
    "\n",
    "class SubsequenceAutomaton1:\n",
    "    __slots__ = (\"_s\", \"_nexts\", \"_charset\", \"_offset\")\n",
    "\n",
    "    def __init__(self, s: str, charset=26, offset=97) -> None:\n",
    "        \"\"\"O(charset*n) 预处理.\n",
    "\n",
    "        Args:\n",
    "            s (str): 待匹配的字符串\n",
    "            charset (int, optional): 字符集大小. 默认为 26.\n",
    "            offset (int, optional): 字符集的起始字符. 默认为 97.\n",
    "        \"\"\"\n",
    "        self._s = s\n",
    "        self._charset = charset\n",
    "        self._offset = offset\n",
    "        self._nexts = self._build()\n",
    "        \"\"\"\n",
    "        _nexts[i][j] 表示在 i 右侧的字符 j 的最近位置 (右侧表示下标严格大于i).\n",
    "        如果不存在，则为 n.\n",
    "        \"\"\"\n",
    "\n",
    "    def move(self, pos: int, char: str) -> int:\n",
    "        \"\"\"\n",
    "        查询当前位置的下一个特定字符的位置(下标严格大于pos).\n",
    "        如果不存在，则为 n.\n",
    "        0<=pos<n.\n",
    "        \"\"\"\n",
    "        return self._nexts[pos][ord(char) - self._offset]\n",
    "\n",
    "    def includes(self, t: str, sStart=0, sEnd=-1, tStart=0, tEnd=-1) -> bool:\n",
    "        \"\"\"\n",
    "        查询s[sStart:sEnd]是否含有某序列t[tStart:tEnd].\n",
    "        时间复杂度O(len(t)).\n",
    "        \"\"\"\n",
    "        hit, _ = self.match(t, sStart=sStart, sEnd=sEnd, tStart=tStart, tEnd=tEnd)\n",
    "        if tEnd == -1:\n",
    "            tEnd = len(t)\n",
    "        return hit >= tEnd - tStart\n",
    "\n",
    "    def match(self, t: str, sStart=0, sEnd=-1, tStart=0, tEnd=-1) -> Tuple[int, int]:\n",
    "        \"\"\"\n",
    "        在 s[sStart:sEnd] 中寻找子序列 t[tStart:tEnd].\n",
    "        时间复杂度 O(len(t)).\n",
    "\n",
    "        Args:\n",
    "            t: 待匹配的子序列\n",
    "            sStart: s的起始索引\n",
    "            sEnd: s的结束索引\n",
    "            tStart: t的起始索引\n",
    "            tEnd: t的结束索引\n",
    "        Returns:\n",
    "            (hit,end): (`匹配到的的t的长度`, `匹配结束时s的索引`)\n",
    "        \"\"\"\n",
    "        if sEnd == -1:\n",
    "            sEnd = len(self._s)\n",
    "        if sStart >= sEnd:\n",
    "            return 0, sStart\n",
    "        if tEnd == -1:\n",
    "            tEnd = len(t)\n",
    "        if tStart >= tEnd:\n",
    "            return 0, sStart\n",
    "\n",
    "        n = len(self._s)\n",
    "        si, ti = sStart, tStart\n",
    "        if self._s[sStart] == t[tStart]:\n",
    "            ti += 1\n",
    "        while si < sEnd and ti < tEnd:\n",
    "            nextPos = self.move(si, t[ti])\n",
    "            if nextPos == n:\n",
    "                return ti - tStart, si\n",
    "            si, ti = nextPos, ti + 1\n",
    "        return ti - tStart, si\n",
    "\n",
    "    def _build(self) -> List[Tuple[int]]:\n",
    "        n = len(self._s)\n",
    "        nexts = [None] * n\n",
    "        last = [n] * self._charset\n",
    "        offset = self._offset\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            nexts[i] = tuple(last)  # type: ignore\n",
    "            last[ord(self._s[i]) - offset] = i\n",
    "        return nexts  # type: ignore\n",
    "\n",
    "\n",
    "V = TypeVar(\"V\")\n",
    "\n",
    "\n",
    "class SubsequenceAutomaton2(Generic[V]):\n",
    "    __slots__ = (\"_seq\", \"_indexes\")\n",
    "\n",
    "    def __init__(self, seq: Sequence[V]) -> None:\n",
    "        \"\"\"O(n) 预处理.\"\"\"\n",
    "        self._seq = seq\n",
    "        self._indexes = self._build()\n",
    "\n",
    "    def move(self, pos: int, newValue: V) -> int:\n",
    "        \"\"\"\n",
    "        查询当前位置的下一个特定字符的位置(下标严格大于pos).\n",
    "        如果不存在，则为 n.\n",
    "        0<=pos<n\n",
    "        \"\"\"\n",
    "        indexes = self._indexes[newValue]\n",
    "        nextPos = bisect_right(indexes, pos, lo=pos)\n",
    "        return indexes[nextPos] if nextPos < len(indexes) else len(self._seq)\n",
    "\n",
    "    def includes(self, t: Sequence[V], sStart=0, sEnd=-1, tStart=0, tEnd=-1) -> bool:\n",
    "        \"\"\"\n",
    "        查询s[sStart:sEnd]是否含有某序列t[tStart:tEnd].\n",
    "        时间复杂度O(len(t)logn).\n",
    "        \"\"\"\n",
    "        hit, _ = self.match(t, sStart=sStart, sEnd=sEnd, tStart=tStart, tEnd=tEnd)\n",
    "        if tEnd == -1:\n",
    "            tEnd = len(t)\n",
    "        return hit >= tEnd - tStart\n",
    "\n",
    "    def match(self, t: Sequence[V], sStart=0, sEnd=-1, tStart=0, tEnd=-1) -> Tuple[int, int]:\n",
    "        \"\"\"\n",
    "        在 s[sStart:sEnd] 中寻找子序列 t[tStart:tEnd].\n",
    "        时间复杂度 O(len(t)logn).\n",
    "\n",
    "        Args:\n",
    "            t: 待匹配的子序列\n",
    "            sStart: s的起始索引\n",
    "            sEnd: s的结束索引\n",
    "            tStart: t的起始索引\n",
    "            tEnd: t的结束索引\n",
    "        Returns:\n",
    "            (hit,end): (`匹配到的的t的长度`, `匹配结束时s的索引`)\n",
    "            此时,匹配结束时t的索引为`tStart+hit`.\n",
    "            耗去的s的长度为`end-sStart`.\n",
    "        \"\"\"\n",
    "        if sEnd == -1:\n",
    "            sEnd = len(self._seq)\n",
    "        if sStart >= sEnd:\n",
    "            return 0, sStart\n",
    "        if tEnd == -1:\n",
    "            tEnd = len(t)\n",
    "        if tStart >= tEnd:\n",
    "            return 0, sStart\n",
    "\n",
    "        n = len(self._seq)\n",
    "        si, ti = sStart, tStart\n",
    "        if self._seq[sStart] == t[tStart]:  # !注意需要先判断第一个字符\n",
    "            ti += 1\n",
    "        while si < sEnd and ti < tEnd:\n",
    "            nextPos = self.move(si, t[ti])\n",
    "            if nextPos == n:\n",
    "                return ti - tStart, si\n",
    "            si, ti = nextPos, ti + 1\n",
    "        return ti - tStart, si\n",
    "\n",
    "    def _build(self) -> DefaultDict[V, List[int]]:\n",
    "        indexes = defaultdict(list)\n",
    "        for i, char in enumerate(self._seq):\n",
    "            indexes[char].append(i)\n",
    "        return indexes\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n",
    "        SA = SubsequenceAutomaton1(S)\n",
    "        return sum(SA.includes(word) for word in words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n",
    "        nxt = [[-1]*26 for _ in range(len(s)+1)]\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            for j in range(26): nxt[i+1][j] = nxt[0][j]\n",
    "            nxt[0][ord(s[i])-ord('a')] = i+1\n",
    "        ans = 0\n",
    "        for w in words:\n",
    "            i = 0\n",
    "            for c in w:\n",
    "                if i == -1: break\n",
    "                i = nxt[i][ord(c)-ord('a')]\n",
    "            if i != -1: ans += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
